﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace LeetCodeSolutions
{
    /// <summary>
    /// LCR 017. 最小覆盖子串
    /// https://leetcode.cn/problems/M1oyTv/description/
    /// </summary>
    class LeetCodeLCR017 : LeetCodeBase
    {
        public override void Execute()
        {
            string s = "wegdtzwabazduwwdysdetrrctotpcepalxdewzezbfewbabbseinxbqqplitpxtcwwhuyntbtzxwzyaufihclztckdwccpeyonumbpnuonsnnsjscrvpsqsftohvfnvtbphcgxyumqjzltspmphefzjypsvugqqjhzlnylhkdqmolggxvneaopadivzqnpzurmhpxqcaiqruwztroxtcnvhxqgndyozpcigzykbiaucyvwrjvknifufxducbkbsmlanllpunlyohwfsssiazeixhebipfcdqdrcqiwftutcrbxjthlulvttcvdtaiwqlnsdvqkrngvghupcbcwnaqiclnvnvtfihylcqwvderjllannflchdklqxidvbjdijrnbpkftbqgpttcagghkqucpcgmfrqqajdbynitrbzgwukyaqhmibpzfxmkoeaqnftnvegohfudbgbbyiqglhhqevcszdkokdbhjjvqqrvrxyvvgldtuljygmsircydhalrlgjeyfvxdstmfyhzjrxsfpcytabdcmwqvhuvmpssingpmnpvgmpletjzunewbamwiirwymqizwxlmojsbaehupiocnmenbcxjwujimthjtvvhenkettylcoppdveeycpuybekulvpgqzmgjrbdrmficwlxarxegrejvrejmvrfuenexojqdqyfmjeoacvjvzsrqycfuvmozzuypfpsvnzjxeazgvibubunzyuvugmvhguyojrlysvxwxxesfioiebidxdzfpumyon";
            string t = "ozgzyywxvtublcl";
            CommonFuntions.Print(MinWindow(s, t));
        }

        /// <summary>
        /// 输入：s = "ADOBECODEBANC", t = "ABC"
        /// 输出："BANC" 
        /// 解释：最短子字符串 "BANC" 包含了字符串 t 的所有字符 'A'、'B'、'C'
        /// </summary>
        /// <param name="longStr"></param>
        /// <param name="shortStr"></param>
        /// <returns></returns>
        public string MinWindow(string longStr, string shortStr)
        {
            if (shortStr.Length > longStr.Length)
            {
                return "";
            }

            Dictionary<char, int> shortStrChNumDic = new Dictionary<char, int>(); //短串中 每个字符的个数
            foreach (char ch in shortStr)
            {
                if (shortStrChNumDic.ContainsKey(ch))
                {
                    shortStrChNumDic[ch]++;
                    continue;
                }
                shortStrChNumDic[ch] = 1;
            }
            int minResultLength = shortStrChNumDic.Count; //结果的最小长度 也就是短串中有多少个字符
            List<string> targets = new List<string>(); //所有子串
            for (int i = 0; i < longStr.Length; i++)
            {
                for (int j = i + 1; j <= longStr.Length; j++)
                {
                    string target = longStr.Substring(i, j - i);
                    //Console.WriteLine(string.Format("i: {0}, j: {1}, value: {2}", i, j, target));
                    targets.Add(target);
                }
            }

            //Console.WriteLine("========================================");

            List<string> results = new List<string>(); //符合结果的子串
            for (int i = 0; i < targets.Count; i++)
            {
                string target = targets[i];
                if (target.Length < minResultLength)
                {
                    continue;
                }
                if (shortStrChNumDic.Any(kvp => !target.Contains(kvp.Key)))
                {
                    continue;
                }
                //对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
                if (shortStrChNumDic.Any(kvp => target.Where(ch => ch == kvp.Key).Count() < kvp.Value))
                { 
                    continue;
                }

                results.Add(target);
                //Console.WriteLine(string.Format("add target: {0}", target));
            }

            if (results.Count == 0)
            {
                return "";
            }

            return results.OrderBy(str => str.Length).First();
        }
    }
}
